#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e9+7;
const int N=2000+5;
ll T,n,a[N],c[N];
ll dp[N][N][2];
void solve1(){
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    ll ans=0;
    for(int msk=0;msk<(1<<n);msk++){
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++){
            if(msk>>i&1){
                c[i]=1;}}
        ll sum=0;
        for(int i=0;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(c[i]==c[j]){
                    if(a[i]==a[j]){
                        sum+=a[i];}
                    break;}}}
        ans=max(ans,sum);}
    printf("%lld\n",ans);}
void solve2(){
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    memset(dp,0,sizeof(dp));
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            dp[i][j][0]=dp[i-1][0][1]+(a[i]==a[i-j-1])*a[i];
            dp[i][j][1]=dp[i-1][0][0]+(a[i]==a[i-j-1])*a[i];
            ans=max(ans,dp[i][j][0]);
            ans=max(ans,dp[i][j][1]);}
        for(int j=0;j<i-1;j++){
            dp[i][0][0]=max(dp[i][0][0],dp[i-1][j][0]+(a[i]==a[i-1])*a[i]);
            dp[i][0][1]=max(dp[i][0][1],dp[i-1][j][1]+(a[i]==a[i-1])*a[i]);
            ans=max(ans,dp[i][0][0]);
            ans=max(ans,dp[i][0][1]);}
        for(int j=1;j<i-1;j++){
            dp[i][1][0]=max(dp[i][1][0],dp[i-1][j][1]+(a[i]==a[i-2])*a[i]);
            dp[i][1][1]=max(dp[i][1][1],dp[i-1][j][0]+(a[i]==a[i-2])*a[i]);
            ans=max(ans,dp[i][1][0]);
            ans=max(ans,dp[i][1][1]);}}
    cout<<ans<<"\n";}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        if(n<=15)solve1();
        else if(n<=2000)solve2();}
    return 0;
}